import random
import math
from threading import Thread

def nthPrime(n,which=1):
    global p1
    global p2
    k=0
    p=1
    while k<n:
        p+=1
        if isPrime(p):
            k+=1
    if which == 1:
        p1 = p
    else:
        p2 = p
    return p

def isPrime(p):
    for i in range(2,int(p ** (0.5))+1):
        if p%i==0:
            return False
    return True
def gcd(a, b):
    g = a % b
    while (a>1) and (b>1) and (a % b <> 0):
        if a > b:
            a = a % b
        else:
            b = b % a
    return a
def modulo(a,b,c):
    x=1
    y=a
    while b>0:
        if b%2==1:
            x=(x*y)%c
        y=(y*y)%c
        b/=2
    return int(x%c)
"""def totient(n):
    count=0
    i=1
    while i<n:
        if gcd(n,i)==1:
            count+=1
        i+=1
    print "the totient of n is count",n,count
    return count"""
def totient(n):
         tot, pos = 0, n-1
         while pos>0:
            if gcd(pos,n)==1: tot += 1
            pos -= 1
         return tot
def mod_inverse(base, mod):
    tot=totient(mod)-1
    print "totient complete"
    inv=modulo(base,tot,mod)
    print "modulo complete"
    return inv
def endecrypt(msg_or_cipher,key,mod):
    return modulo(msg_or_cipher, key,mod)
"""
def coprime(n):
    coprimes={}
    i=1
    c=0
    while i<n:
        if gcd(n,i)==1:

             coprimes[c]=i
             c+=1
        i+=1
    n=random.randint(0,len(coprimes)-1)
    return coprimes[n]
"""
def coprime(n):
    i=n*2
    found = False
    while found == False:
        if gcd(n,i)==1:
            found = True
        if found!=True:
            i+=1
    return i


#print nthPrime(2)
global p1
global p2
a,b=input("Please give two numbers:")
t1 = Thread(target=nthPrime, args=(a,1,))
t2 = Thread(target=nthPrime, args=(b,2,))
#a=nthPrime(a)
#b=nthPrime(b)
t1.start()
t2.start()
t1.join()
t2.join()
a = p1
b = p2
print "Primes: ", a, b
c=a*b
m=(a-1)*(b-1)
e=coprime(m)
d=mod_inverse(e,m)
print "A: "+str(a)

print "B: "+str(b)

print "C: "+str(c)

print "M: "+str(m)

print "E: "+str(e)

print "D: "+str(d)

print endecrypt(endecrypt(2324,e,c),d,c)
